<?php
	
	namespace org\tekuna\core\util;

	
	/**
	 * This class implements a queue whose elements are sorted by 
	 * a certain weight. Elements with lower weight are returned
	 * prior elements with higher weight when iterating through 
	 * the queue.
	 * 
	 * This queue supports two "special weights": min and max. An
	 * element inserted with min weight is always returned first; 
	 * an element with max weight is always returned last.
	 * 
	 * Insertion order is preserved in case of equal weights (even
	 * the special weights).
	 */
	class WeightedList {
		
		const
			MIN_WEIGHT = 'min',
			MAX_WEIGHT = 'max';
		
		private
			$arrData = array();
			
		
		/**
		 * Add new element with the given weight to the list.
		 * List is sorted automatically after this step.
		 * 
		 * @param mixed $objElement the element to insert
		 * @param mixed $sWeight the weight of the element
		 */
		public function addElement($objElement, $sWeight) {
			
			// since PHP's sort functions are not stable (they do not
			// keep the order of insertion) we use some kind of poor
			// man's stable sort here by adding a minimal value to the
			// weight
			static $fWeightAdd = 0;
			if ($sWeight != self :: MIN_WEIGHT && $sWeight != self :: MAX_WEIGHT) {
			
				$fWeightAdd += 0.0000000001;
				$sWeight = ((float) $sWeight) + $fWeightAdd;
			}
			
			// insert element in data array
			$this -> arrData[] = array('element' => $objElement, 'weight' => $sWeight);
			
			// sort array
			usort($this -> arrData, array($this, 'compare'));
		}
		
		
		/**
		 * @param boolean $bGetWeights optional; if set to true
		 *        an array with keys 'element' and 'weight' is
		 *        returned for each list element.
		 *        
		 * @return returns according to weights sorted list of 
		 *         elements.
		 */
		public function getSortedList($bGetWeights = false) {
		
			if ($bGetWeights) {
				
				return $this -> arrData;
			}
			else {
				
				$arrElements = array();
				foreach ($this -> arrData as $arrItem) {
					
					$arrElements[] = $arrItem['element'];
				}
				
				return $arrElements;
			}
		}
			

		private function compare($arrItem1, $arrItem2) {
			
			$sWeight1 = $arrItem1['weight'];
			$sWeight2 = $arrItem2['weight'];
			
			// special case: both weights are min or max
			// order is then always 1 (same as inserted)
			if ($sWeight1 == self :: MIN_WEIGHT && $sWeight2 == self :: MIN_WEIGHT ||
			    $sWeight1 == self :: MAX_WEIGHT && $sWeight2 == self :: MAX_WEIGHT) {
				
				return 1;
			}

			// special case: w1 is MAX or w2 is MIN
			// order is always 1
			if ($sWeight1 == self :: MAX_WEIGHT || $sWeight2 == self :: MIN_WEIGHT) {
				
				return 1;
			}
			
			// special case: w1 is MIN or w2 is MAX
			// order is always -1
			if ($sWeight1 == self :: MIN_WEIGHT || $sWeight2 == self :: MAX_WEIGHT) {
				
				return -1;
			}
			
			// conversion to float to perform numerical comparison
			$fWeight1 = (float) $sWeight1;
			$fWeight2 = (float) $sWeight2;

			if ($fWeight1 === $fWeight2) { return 0; }
			return ($fWeight1 < $fWeight2) ? -1 : 1;
		}
	}